package com.fr.lintcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月22日
*时间：上午11:06:27
*/
public class Q127 {
    class DirectedGraphNode {
        int label;
        ArrayList<DirectedGraphNode> neighbors;

        DirectedGraphNode(int x) {
            label = x;
            neighbors = new ArrayList<DirectedGraphNode>();
        }

        @Override
        public String toString() {
            return label + "-->";
        }

    };

    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        ArrayList<DirectedGraphNode> rs = new ArrayList<>();
        List<DirectedGraphNode> all = new ArrayList<>(graph);
        for (DirectedGraphNode d : graph) {
            all.removeAll(d.neighbors);
        }
        if (all.size() <= 0) {
            return rs;
        }
        Map<DirectedGraphNode, Integer> map = new HashMap<>();
        for (DirectedGraphNode d : all) {
            map.put(d, 0);
        }
        bfs(all, map);
        Set<java.util.Map.Entry<DirectedGraphNode, Integer>> set = map.entrySet();
        List<java.util.Map.Entry<DirectedGraphNode, Integer>> list = new ArrayList<>(set);
        Collections.sort(list, new c());
        for (java.util.Map.Entry<DirectedGraphNode, Integer> e : list) {
            rs.add(e.getKey());
        }
        return rs;
    }

    class c implements Comparator<java.util.Map.Entry<DirectedGraphNode, Integer>> {

        @Override
        public int compare(Entry<DirectedGraphNode, Integer> o1, Entry<DirectedGraphNode, Integer> o2) {
            // TODO Auto-generated method stub
            return o1.getValue() - o2.getValue();
        }

    }

    private void bfs(List<DirectedGraphNode> all, Map<DirectedGraphNode, Integer> map) {
        if (all.size() > 0) {
            Set<DirectedGraphNode> tmp = new HashSet<>();
            for (DirectedGraphNode d : all) {
                Integer path = map.get(d);
                path = path == null ? 0 : path;
                for (DirectedGraphNode n : d.neighbors) {
                    map.put(n, path + 1);
                    tmp.add(n);
                }
            }
            all = new ArrayList<>(tmp);
            bfs(all, map);
        }
    }

    @Test
    public void testA() {
        DirectedGraphNode n1 = new DirectedGraphNode(1);
        DirectedGraphNode n2 = new DirectedGraphNode(2);
        DirectedGraphNode n3 = new DirectedGraphNode(3);
        DirectedGraphNode n4 = new DirectedGraphNode(4);
        DirectedGraphNode n5 = new DirectedGraphNode(5);
        n1.neighbors.add(n2);
        n1.neighbors.add(n3);
        n2.neighbors.add(n4);
        n2.neighbors.add(n5);
        ArrayList<DirectedGraphNode> graph = new ArrayList<>();
        graph.add(n1);
        graph.add(n2);
        graph.add(n3);
        graph.add(n4);
        graph.add(n5);
        ArrayList<DirectedGraphNode> rs = topSort(graph);
        System.out.println(rs);

    }
}
